package jzOffer;

import java.util.Deque;
import java.util.LinkedList;

public class Num59of1 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==0 || k==0) return new int[0];
        int[] res=new int[nums.length-k+1];
        Deque<Integer> deque =new LinkedList<>();
        for(int j=0,i=1-k;j<nums.length;j++,i++){
            if(i>0 && nums[i-1]==deque.peekFirst()){
                deque.removeFirst();
            }
            while(!deque.isEmpty() && nums[j]>deque.peekLast()){
                deque.removeLast();
            }
            deque.addLast(nums[j]);
            if(i>=0){
                res[i]=deque.peekFirst();
            }
        }
        return res;
    }
}
